/**
 * @author Bernhard Denner
 * @author Maximilian Csuk
 * @author Konrad Paumann
 */

public class Tree<N extends Better<? super N>, E> {
	
	private N nodeTitle = null;
	private child firstChild = null;
	
	private class child {
		E edgeTitle;
		Tree<N, E> node;
		child next;
		
		child(E edgeTitle, Tree<N, E> node) {
			this.edgeTitle = edgeTitle;
			this.node = node;
		}
	}
	
	private abstract class ChildIterator implements TreeIterator<N, E> {
		child curChild = null;
		child nextChild = firstChild;
		
		/**
		 * Checks if there exists a next Element
		 * Returns true if yes, false otherwise
		 */
		public boolean hasNext() {
			if (curChild == null)
				nextChild = firstChild;
			
			return nextChild != null;
		}
		/**
		 * Inserts a node in the tree
		 * Returns 	true if node has been successfully inserted,
		 * 			false otherwise
		 */
		public boolean insert (E edge, N node) {
			child newChild = new child(edge, new Tree<N, E>(node));
			
			if (curChild == null){
				if (newChild.node.nodeTitle.better(nodeTitle)) {
					newChild.next = firstChild;
					firstChild = nextChild = newChild;
					return true;
				} else {
					newChild = null;
					return false;
				}
				
			} else {
				if (newChild.node.nodeTitle.better(curChild.node.nodeTitle)) {
					newChild.next = nextChild;
					curChild.next = nextChild = newChild;
					return true;
				}
				else {
					newChild = null;
					return false;
				}
			}
		}
	}
	
	private class NodeIterator 	extends ChildIterator 
								implements TreeNodeIterator<N, E> {
		/**
		 * Returns the next Node
		 */
		public Tree<N, E> next(){
			if (curChild == null)
				nextChild = firstChild;
			
			if (nextChild == null)
				return null;
			
			curChild = nextChild;
			nextChild = nextChild.next;
			return curChild.node;
		}
	}
	
	private class EdgeIterator 	extends ChildIterator 
								implements TreeEdgeIterator<N, E> {
		/**
		 * Returns the next Edge
		 */
		public E next() {
			if (curChild == null)
				nextChild = firstChild;
			
			if (nextChild == null) 
				return null;
			
			curChild = nextChild;
			nextChild = nextChild.next;
			return curChild.edgeTitle;
		}
	}
	
	public Tree (N nodeTitle) {
		this.nodeTitle = nodeTitle;
	}
	/**
	 * Returns the title of the node
	 */
	public N getNodeTitle() {
		return nodeTitle;
	}
	/**
	 * Returns an Iterator for the Edges of a node
	 */
	public TreeEdgeIterator<N, E> getEdgeIterator() {
		return new EdgeIterator();
	}
	/**
	 * Returns an Iterator for the nodes of the tree
	 */
	public TreeNodeIterator<N, E> getNodeIterator() {
		return new NodeIterator();
	}
}
